package com.leetcode.tree.recursion;

import com.leetcode.basic.TreeNode;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/10/17 16:29
 */
public class FindDuplicateSubtrees_652 {

    List<TreeNode> res = new ArrayList<>();
    Map<Integer, Set<TreeNode>> map = new HashMap<>();
    Set<TreeNode> added = new HashSet<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        dfs(root);
        res.addAll(added);
        return res;
    }

    public void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        dfs(root.right);
        int key = root.val;
        if (!map.containsKey(key)) {
            Set<TreeNode> set = new HashSet<>();
            set.add(root);
            map.put(key, set);
        } else {
            Set<TreeNode> set = map.get(key);
            boolean showed = false;
            for (TreeNode node : set) {
                if (isSame(node, root)) {
                    added.add(node);
                    showed = true;
                    break;
                }
            }
            if (!showed)
                set.add(root);
        }
    }

    private boolean isSame(TreeNode newNode, TreeNode node) {
        if (newNode == null && node == null) return true;
        if (newNode == null || node == null || newNode.val != node.val) return false;
        return isSame(newNode.left, node.left) && isSame(newNode.right, node.right);
    }

}
